package Ch_2_4_Priority_Queues;

import java.util.*;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;

public class Practise_2_4_28 {
    static class Coordinate implements Comparable<Coordinate> {
        public final double x;
        public final double y;
        public final double z;
        public final double dis;
        public Coordinate(double x, double y, double z) {
            this.x = x; this.y = y; this.z = z;
            this.dis = Math.sqrt(x * x + y * y + z * z);
        }
        public int compareTo(Coordinate other) {
            return dis < other.dis ? -1 : dis > other.dis ? 1 : 0;
        }
        public String toString() {
            return String.format("{ %-8.1f, \t%-8.1f, \t%-8.1f \t} \t= %-8.3f", x, y, z, dis);
        }
    }
    static class TopM {
        private Coordinate[] cors = new Coordinate[2];
        private int size;
        public boolean isEmpty() { return size == 0; }
        public void resize(int newSize) {
            Coordinate[] newC = new Coordinate[newSize + 1];
            for (int i = 1; i <= size; i++)
                newC[i] = cors[i];
            cors = newC;
        }
        public void insert(Coordinate c) {
            if (size == cors.length - 1)
                resize(size << 1);
            int k = ++size;
            while (k > 1 && cors[k >> 1].compareTo(c) > 0) {
                cors[k] = cors[k >> 1];
                k >>= 1;
            }
            cors[k] = c;
        }
        public Coordinate delMin() {
            if (isEmpty())
                throw new NoSuchElementException("priority queue underflow");
            Coordinate min = cors[1];
            cors[1] = cors[size];
            int k = 1;
            Coordinate last = cors[size--];
            while ((k << 1) <= size) {
                int j = k << 1;
                if (cors[j].compareTo(cors[j + 1]) > 0) j++;
                if (last.compareTo(cors[j]) <= 0) break;
                cors[k] = cors[j];
                k = j;
            }
            cors[k] = last;
            cors[size + 1] = null;
            if (size > 0 && size == (cors.length - 1) >> 2)
                resize((cors.length - 1) >> 1);
            return min;
        }
    }
    public static Coordinate[] randomGen(int N) {
        Coordinate[] c = new Coordinate[N];
        double lo = -N * 100;
        double hi = N * 100;
        for (int i = 0; i < N; i++)
            c[i] = new Coordinate(StdRandom.uniform(lo, hi),
                                  StdRandom.uniform(lo, hi),
                                  StdRandom.uniform(lo, hi));
        return c;
    }
    public static void main(String[] args) {
        int N = 100000, M = 100;
        TopM m = new TopM();
        for (Coordinate c : randomGen(N))
            m.insert(c);
        while (M-- > 0)
            StdOut.println(m.delMin());
    }
    // output
    /*
     *  { -29669.1,  240295.8,   45477.5     }   = 246354.463
        { 212141.7,     25121.6 ,   250270.3    }   = 329044.652
        { 15520.8 ,     -385425.1,  98945.2     }   = 398225.498
        { -279974.2,    -34037.8,   -403089.2   }   = 491960.345
        { -185112.8,    -318003.1,  340765.1    }   = 501511.267
        { 85837.0 ,     -153728.2,  -483898.6   }   = 514935.116
        { 533047.5,     41145.0 ,   -29211.0    }   = 535430.501
        { -69894.9,     -504412.3,  175528.5    }   = 538634.675
        { -460107.8,    -147378.8,  -421267.9   }   = 641004.189
        { -242054.0,    395445.0,   502867.4    }   = 683990.146
        { 424985.7,     315517.9,   -463501.5   }   = 703560.939
        { 420928.3,     -200255.4,  -559892.0   }   = 728534.125
        { -679132.1,    -158898.2,  -211808.5   }   = 728925.143
        { -322284.3,    329986.7,   590724.4    }   = 749475.644
        { 481868.0,     -515683.2,  -266835.2   }   = 754537.609
        { 472134.0,     262962.3,   530945.2    }   = 757603.091
        { -738010.6,    72790.9 ,   193839.9    }   = 766506.413
        { -95242.4,     -770652.6,  -195179.7   }   = 800669.552
        { 175120.5,     321159.8,   -726972.1   }   = 813817.664
        { 805430.9,     -155872.6,  86897.9     }   = 824964.501
        { 101971.1,     798626.6,   -193024.4   }   = 827925.671
        { 176042.1,     393204.6,   709101.4    }   = 829714.081
        { -846915.9,    -8253.0 ,   -8886.5     }   = 847002.708
        { 457413.6,     734461.9,   69715.5     }   = 868056.278
        { 245633.7,     -554231.4,  636189.4    }   = 878774.889
        { -431430.5,    697592.1,   315623.2    }   = 878854.388
        { 343296.8,     -250375.2,  775341.9    }   = 884135.443
        { -770372.1,    -288468.5,  329910.9    }   = 886300.408
        { -787657.4,    -317889.8,  272044.2    }   = 891889.039
        { 474852.3,     -704961.0,  273114.7    }   = 892774.568
        { -615379.5,    -468474.1,  458961.3    }   = 899336.100
        { 799528.5,     -397400.8,  136140.9    }   = 903165.305
        { -385295.1,    565736.7,   -607969.0   }   = 915498.013
        { -641890.3,    653111.7,   -52823.4    }   = 917261.359
        { -908076.2,    87815.5 ,   131561.0    }   = 921749.566
        { -120722.1,    -906423.0,  184575.6    }   = 932869.056
        { 31363.1 ,     -912854.5,  -207731.0   }   = 936717.201
        { -941834.4,    106835.9,   -30247.2    }   = 948356.869
        { 327165.3,     885269.2,   -97295.1    }   = 948791.366
        { -661069.1,    -340532.6,  606716.9    }   = 959729.298
        { 529946.3,     -657197.2,  -516788.1   }   = 989859.155
        { 50044.5 ,     -992567.3,  -21750.9    }   = 994066.133
        { -507595.7,    -164738.0,  859055.7    }   = 1011320.233
        { -979985.9,    -123596.1,  229931.7    }   = 1014158.273
        { 896019.4,     479967.0,   83865.0     }   = 1019927.659
        { -298446.5,    -492838.6,  857264.9    }   = 1032890.763
        { 227401.7,     969410.5,   312470.3    }   = 1043602.409
        { 1020513.1,    -259334.9,  32504.6     }   = 1053450.547
        { -223202.1,    1017892.6,  -158109.5   }   = 1054003.350
        { 225974.1,     61011.9 ,   1031525.6   }   = 1057748.438
        { 1010396.2,    -171924.4,  -269857.2   }   = 1059849.654
        { 85263.6 ,     -1061452.8,     44067.0     }   = 1065783.233
        { 879054.0,     604575.1,   45885.5     }   = 1067872.855
        { 811586.4,     -332575.0,  -609914.8   }   = 1068304.552
        { 558511.4,     827071.1,   -398854.7   }   = 1074740.285
        { -659559.1,    -856481.2,  28731.1     }   = 1081389.742
        { 570886.7,     248630.9,   892165.3    }   = 1087974.236
        { 72241.1 ,     -907701.2,  -631646.8   }   = 1108204.803
        { 608776.6,     -920676.9,  -139195.7   }   = 1112488.331
        { -219619.8,    911564.4,   615622.8    }   = 1121683.530
        { -702114.1,    -214738.0,  -850777.6   }   = 1123787.848
        { -1063705.9,   -145524.9,  352218.5    }   = 1129913.976
        { -37901.0,     -375949.6,  1065927.9   }   = 1130918.574
        { 988318.7,     -340074.4,  439324.0    }   = 1133767.996
        { 928898.9,     174914.5,   -647816.7   }   = 1145912.200
        { -159346.9,    248278.3,   -1110808.9  }   = 1149317.132
        { 1061897.0,    -205507.5,  -403945.6   }   = 1154569.427
        { 911015.5,     -31805.6,   -712135.5   }   = 1156761.789
        { 358663.9,     -1105762.7,     90792.9     }   = 1166016.420
        { -662912.8,    -692992.5,  664727.1    }   = 1166856.526
        { 410734.8,     495260.2,   -981877.7   }   = 1173912.098
        { 892109.5,     658065.7,   -387606.7   }   = 1174371.651
        { 206060.5,     -838373.3,  797185.8    }   = 1175089.769
        { -1136873.2,   -160960.9,  -278511.1   }   = 1181506.422
        { 1078268.4,    197454.3,   -447239.1   }   = 1183922.993
        { -342533.0,    -661169.3,  922402.1    }   = 1185453.212
        { -793198.1,    -822577.1,  -320692.7   }   = 1186861.480
        { -704778.9,    -921277.8,  257087.6    }   = 1188090.995
        { -68073.6,     -376198.9,  1126519.6   }   = 1189624.303
        { -1175989.8,   -187409.0,  46337.4     }   = 1191730.415
        { -215915.1,    -1003362.9,     625953.2    }   = 1202153.854
        { 265243.8,     349029.1,   -1128823.0  }   = 1210957.044
        { 946972.9,     -724879.5,  278769.6    }   = 1224712.404
        { -163894.7,    -481300.9,  -1124043.0  }   = 1233687.406
        { 536705.2,     -908838.6,  -644209.7   }   = 1236546.111
        { 393149.8,     -32870.2,   -1172340.9  }   = 1236943.973
        { 158534.0,     -1167940.2,     -411512.8   }   = 1248423.037
        { 86952.8 ,     -208502.5,  -1227990.8  }   = 1248597.449
        { 89117.2 ,     239256.9,   1230914.4   }   = 1257114.128
        { -831344.4,    794241.8,   -511469.8   }   = 1258393.781
        { -410412.5,    -1181056.5,     -244952.2   }   = 1274101.423
        { -720038.3,    649863.1,   -839160.5   }   = 1282562.836
        { 512387.6,     571218.2,   -1027829.5  }   = 1282678.797
        { -1106100.1,   330782.9,   581795.4    }   = 1292811.086
        { -1130376.1,   197003.5,   -606555.0   }   = 1297871.162
        { 390700.1,     -997024.0,  744239.0    }   = 1304068.643
        { -1201395.2,   436405.2,   -273836.4   }   = 1307205.578
        { 458442.8,     -997258.9,  -712044.3   }   = 1308320.442
        { -867354.5,    637917.0,   750152.6    }   = 1312238.834
        { 808411.0,     201925.4,   -1015326.6  }   = 1313464.945
     */
}
